package graph

import "gitee.com/kklt1996/data-structure/common"

/*
   使用邻接矩阵的方式表示稠密图, 无权图
   邻接矩阵能表达自环边和处理平行边的问题，能表示自环边，能过滤掉平行边
*/
type DenseGraph struct {
	// 顶点的数量
	n int
	// 边的数量
	m int
	// 是否是有向图
	directed bool
	// 边的表示
	g [][]bool
}

/*
	顶点数量
*/
func (graph DenseGraph) V() int {
	return graph.n
}

/*
	边的数量
*/
func (graph DenseGraph) E() int {
	return graph.m
}

/*
   添加边，也就是连接两个顶点
*/
func (graph *DenseGraph) AddEdge(v int, w int) {
	if graph.HasEdge(v, w) {
		// 已经有边了，不需要添加
		return
	}

	graph.g[v][w] = true

	if !graph.directed {
		// 无向图的话需要连接w->v
		graph.g[w][v] = true
	}

	graph.m++
}

/*
	删除边
*/
func (graph *DenseGraph) RemoveEdge(v int, w int) {
	if !graph.HasEdge(v, w) {
		// 不存在的边直接返回
		return
	}

	graph.g[v][w] = false

	if !graph.directed {
		// 无向图需要删除w->v
		graph.g[w][v] = false
	}

	graph.m--
}

/*
	检查边是否存在
*/
func (graph DenseGraph) HasEdge(v int, w int) bool {
	return graph.g[v][w]
}

/*
	获取某一个顶点相邻顶点的迭代器
*/
func (graph *DenseGraph) VertexIterator(v int) common.ForIntIterator {
	iterator := &DenseVertexIterator{-1, v, graph}
	return iterator
}

type DenseVertexIterator struct {
	// 遍历的index
	index int

	// 需要遍历的顶点v
	v int

	// 图结构
	graph *DenseGraph
}

func (iterator *DenseVertexIterator) Begin() int {
	iterator.index = -1
	return iterator.Next()
}

func (iterator *DenseVertexIterator) Next() int {
	for iterator.index++; iterator.index < len(iterator.graph.g[iterator.v]); iterator.index++ {
		if iterator.graph.g[iterator.v][iterator.index] {
			return iterator.index
		}
	}
	return -1
}

func (iterator *DenseVertexIterator) End() bool {
	return iterator.index >= len(iterator.graph.g[iterator.v])
}
